package _动态规划系列._01背包问题;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/30 20:33
 * <p>
 * 功能描述:
 */
public class test {

    /**
     * dp[i][w]:  前i个商品，当容量为w时，最大价值为dp[i][w]
     */
    int knapsack(int W, int N, int[] wt, int[] val) {
        int[][] dp = new int[W + 1][N + 1];
        //base case  dp[0][] , dp[][0] 为0
        for (int i = 1; i < N + 1; i++) {
            for (int w = 1; w < W + 1; w++) {
                if (w - wt[i - 1] < 0) {
                    dp[i][w] = dp[i - 1][w]; //此时只能选择不放
                } else {
                    dp[i][w] = Math.max(
                            dp[i - 1][w],  //没选第i件商品
                            dp[i - 1][w - wt[i - 1]] + val[i - 1]);   //选了第i件
                    //你选了第i件商品,那么前i-1件商品时，容量就剩(w-第i件容量)
                }
            }
        }

        return dp[N][W];
    }
}
